package shortestpath;

/**
 * 佛洛依德算法求解多顶点间最短路径问题
 *
 * @author zj
 */
public class ShortestPath2 {
    public static int INF = 1000;
    public static int A[][] = {
            {0, 4, 6, 6, INF, INF, INF},
            {INF, 0, 1, INF, 7, INF, INF},
            {INF, INF, 0, INF, 6, 4, INF},
            {INF, INF, 2, 0, INF, 5, INF},
            {INF, INF, INF, INF, 0, INF, 6},
            {INF, INF, INF, INF, 1, 0, 8},
            {INF, INF, INF, INF, INF, INF, 0}
    };

    public static void floyd(int A[][]) {
        int length = A.length;
        int path[][] = new int[length][length];
        int a[][] = new int[length][length];

        for (int i = 0; i < length; i++) {
            for (int j = 0; j < length; j++) {
                a[i][j] = A[i][j];
                path[i][j] = -1;
            }
        }

        for (int k = 0; k < length; k++)
            for (int i = 0; i < length; i++)
                for (int j = 0; j < length; j++)
                    if (a[i][j] > a[i][k] + a[k][j]) {
                        a[i][j] = a[i][k] + a[k][j];
                        path[i][j] = k;
                    }

        for (int i = 0; i < length; i++) {
            for (int j = 0; j < length; j++) {
                if (a[i][j] == INF)
                    System.out.print("INF ");
                else
                    System.out.print(a[i][j] + " ");
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        floyd(A);
    }
}
